#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

#define FOR(i,a,n) for(int i=a,_n(n);i<_n;++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;

const int N = 3000;
const int PARA = 100000000/N;
const int MOD = 1000000007;

int list[N];
int li[]= {74506719,
37828067,428994219,911218960,128243012,560677396,382346703,316632470,492816486,302424119,255567657,837289628,363906113,839350115,811514837,228597044,295440390,329878724,619079438,275886780,95165202,
410142673,948754006,689984185,720211713,89551911,668200280,2775779,172664215,646361521,137817097,462777165,395128054,523239562,106308262,930700857,166297458,222834981,606250418,775024185,996523456,
203345476,849660923,767557179,23381706,774085373,123565734,979010432,907240449,991053496,685567305,674562977,726828295,552501058,659412415,209430178,874802177,694499545,930560094,924431607,953315186,
86508565,41749465,41558886,669584462,726943767,88567663,559543634,731459078,838744669,615017670,149425267,742987903,764942577,509086206,50118938,99987486,864228448,898311627,963983386,885609954,
406520760,45351767,952388799,765910840,468533410,243551864,331284726,885417016,829343570,712512388,566767947,762694535,865959571,493656939,170650322,185916522,448888787,345800138,596026710,108431058,
837705519,640715490,132842804,544329043,576618844,258703254,803463057,464012073,390040527,484158348,258238503,689760338,78152877,901138198,671074697,791300478,412476638,288930622,634999536,981373474,
31438845,517621735,57731171,11302511,335940736,443663784,57245884,66560890,384925594,805443060,857345951,662339863,790946652,118847747,683227512,539116524,615734949,572835841,657048483,558221707,
265767228,925002978,693496405,597407842,387833806,397150339,395356328,446416839,764606444,570852541,949078702,702547972,210206224,283025479,20347219,666225742,465771454,521494238,649646753,236567768,
95025503,320560942,147831160,806952671,379844720,656572659,991691232,160587916,215826276,343489250,719522504,366077745,7856069,928451281,826693194,672991005,565676594,587347858,661212038,407429046,
999454806,20384546,319296188,867593612,615350011,347651232,540939089,219354683,811081757,4689981,605478342,391818401,971497683,638062955,227163595,972894905,364141410,920241,450724427,104866215,
34820432,848567791,546938204,379954151,703173979,834035229,908197977,735888154,658240880,403643784,944080345,351473191,654027475,692574153,976913346,542157646,805075471,420434357,137344320,655601169,
482029819,786827653,259907814,967242574,207206605,366920376,778593424,575867702,550160920,7009851,622413686,299177319,23254723,720092256,110971967,569354979,977224760,581430478,850030342,328634894,
496750378,624122032,627077436,924869839,296021472,734666910,306896350,7098987,614306320,548535465,727132517,421115849,111519460,345736295,593861565,105036081,763789602,946384120,377157222,984865424,
759027456,606267638,206659179,870067525,392493651,912417444,767140974,349131863,962366605,678673865,194077848,685141612,665310374,841254872,969214671,711341497,492042571,354323929,816133756,726705699,
122902215,85557898,595822792,391505718,823417629,711714902,202242693,622878264,339874282,614202188,457895489,490393113,794882722,774644039,9392182,111621005,582946397,670449623,223020658,547701521,
266029574,170380884,80313529,698910939,469125202,430120426,73616038,200230132,775822782,787839369,101653922,316912452,623876251,659765240,365101296,840051586,200771866,435749857,262148523,982149440,
339296081,374837199,284070105,272684023,413103410,500831283,910792553,453677338,232284318,497864041,506462250,375263224,938933105,605963204,215013363,891255268,902715755,516620172,855735699,754714654,
616437848,268357898,818842568,513518068,591612423,142298765,961038695,405925561,254027848,557732463,501088069,256148426,839315718,967683859,915381848,369917082,288518697,754480881,833506201,430048944,
143658444,125322402,933810220,392016307,443303455,7846117,838973776,379514223,618136947,945696413,11575403,580028378,386524742,994092232,649660196,140402962,650083151,615394983,582307639,62408567,
389246830,574676405,165199531,98310043,558836685,835286437,176187849,646434389,983627728,454421095,710862618,646738616,253916954,478690370,78119781,476377645,621091253,839686084,695729118,845272177,
893195238,249549767,985902067,691676556,330499150,96540562,270859636,77746667,541066749,340603074,668400294,85107813,376323156,408935254,987467806,710422578,826622765,91556283,623719138,760958704,
916817092,436874456,455092341,750156989,601822673,647255038,737374414,793199150,662188941,974588162,999769181,502575700,599666089,615856692,940465175,883653839,532772961,608704121,322203515,230245303,
92364922,727002427,867845797,20174283,317201749,376419957,155941929,810845274,549515487,489989318,516298071,134810938,330578340,423675233,925544456,395340037,296270555,851942439,902703295,761985254,
72648285,663323543,404756654,66151091,171511480,855986927,722214338,696661774,885971757,433304597,374681740,495329074,186020263,299420088,6427753,652520240,614095601,154816320,281952633,602725841,
180651644,391883489,781555869,920127664,259725468,990486937,896904067,214166570,484505194,413535022,726598834,25110406,642897879,502547030,971744655,719621854,573097393,373221010,831516756,386326301,
59152296,311001679,898729002,731379758,726533729,666648292,55401753,974036695,937703256,751802512,368329776,742217939,687680776,734556301,984650080,968078558,499612393,535019790,27409807,783575717,
320338286,720889163,491134151,416036576,415960593,403014520,137394165,83726160,267411281,130967775,390374701,891415243,466020037,788610526,232442245,725948197,609082131,489661911,99712822,151810911,
195426300,473266527,777619866,306698654,520982639,999562279,296482076,797083938,574350450,245248250,827071342,593784402,932366147,199152620,576180566,927530710,655671112,557800501,682191588,184534393,
184279593,620981828,110643028,802055775,233146574,187319243,549798198,163971787,687735645,449835979,306212937,496343914,499586879,891523716,200303530,762986016,581884730,180910465,461914564,561032233,
705025889,67628473,625886805,16504862,392187168,277982065,427625082,679882241,814893391,410515535,698666171,421666591,688585243,831581030,262246651,327951942,168187175,570906413,828870816,595991982,
743675281,217163161,891878510,429767934,135645140,813534235,623013039,935556454,190879749,753281936,767989041,17497473,777917358,675315817,542060349,273162130,682619354,359760539,525587889,889120593,
503738159,623523762,559607543,536509957,548485093,215864001,641398033,266602142,728098251,713958538,820048798,406371749,453410380,418471257,92027864,454063937,530416770,249120563,296749749,974762314,
55843110,640247238,12143298,495956793,312713393,436382311,450219602,403111504,665917765,787814963,352639840,835232643,457780416,46160369,886283191,580436349,903627471,659927624,538814676,971516609,
987354839,70087557,14253070,781513100,356996111,605640678,128538765,119279094,220290444,379184992,705101640,325049335,240250417,182483925,470428938,866007895,430729922,382034180,949633171,231856058,
51992034,814633614,362019955,830380232,506276909,682949115,516655936,883019770,233369626,451084493,707936625,320434889,606168106,740148350,611154296,678074547,826250954,223821943,178065863,991744292,
819445357,523927096,532460764,693174160,131394954,105994035,865728817,505586559,823127734,174829307,332428111,339264132,366623864,570083629,945852904,187117641,540383629,661819772,473601451,20253844,
324995260,246080445,333143937,683543379,798702846,440456179,487390319,791188620,32974176,579653183,340258210,622291582,988068672,111061235,632240770,16421784,408605189,490321573,335974562,269184140,
719129976,76894737,551807457,27786808,919684490,29628488,403366483,186609102,481373301,202325657,933125730,782769348,241931976,39312029,997974199,891692761,301294942,471004234,164783700,522679336,
917163370,809477603,605976743,514471725,400573038,644034059,995094373,430823100,11462243,736770001,402364075,456065044,854239657,918144167,190267665,290675421,773352183,982545518,909109146,46846260,
248852874,583861115,192582571,144051632,291968796,131044003,653339976,204615520,340668891,683681088,778559194,949279710,155231868,847560993,825511774,92771640,713814087,670241963,717130844,239372333,
108017408,536619735,937578995,778484218,438457117,64495408,427816144,780199028,710329754,143334,481167439,890865691,728981018,113878981,638891108,228658186,995473644,95626817,585746350,279143448,
602155266,450488194,45561212,790849217,128226315,394309211,676800480,670831922,535307889,749248612,968133521,880244579,63009609,839345642,134002188,329904640,124497538,386087938,10188711,775861905,
202062023,403979413,949383546,714966357,742685593,96108112,716753245,280436074,53610815,749714117,385508375,137425099,197908213,631757389,232471367,378591310,890044103,884485687,633644400,419664297,
391448477,421002410,959777271,895013253,406082915,820834509,471935279,553214830,976008427,225500322,217067116,152621044,376953330,234077500,923572730,356927138,13881160,798770849,896871188,630739452,
316558521,120480207,914968588,135143307,635122962,544368363,124025908,623270903,135650861,455428878,933926918,335869154,695725323,174054004,913846001,896867614,800004015,851602554,687816086,208946305,
435787078,365967751,830296504,349103650,988585004,217145154,761740858,464224301,137686478,422800500,644164914,666647044,751726318,413837588,276714471,929732669,784253282,929966170,991233252,983431847,
169297994,915269807,547830746,209853007,716940821,413773767,30450134,538830234,8879708,465012902,742436145,343491104,293998118,999599511,102102905,335824603,383932853,734791217,538301877,462248983,
548641966,70058865,385989675,799179646,411972624,982654399,781795990,448597014,847228999,923178697,559591432,433614427,872740124,711149504,146055435,594045999,547427791,430569281,456244127,481974502,
866374428,325493089,789158193,257319250,656390955,695596466,723310766,583403976,471584689,791743297,12295304,522524695,488927207,711553705,480353481,431517602,403822223,294971921,917943029,857326942,
325673472,19834168,977305643,432572873,673452587,897436538,68034851,771119378,71266962,368102841,252643912,363642100,243927664,196752538,142133651,473196261,912517275,368468576,791560378,30784504,
689957776,984065279,595603730,530924805,976578452,155656211,184134583,927218315,855683734,902222102,317782915,527917258,989121104,45178648,783505676,891492822,512848951,103944472,290154665,722203001,
932504476,191508938,364044435,765660507,18971527,910000063,244520135,704400626,703948539,246252366,779525415,53449102,975516341,467374794,321170275,55890028,773706082,16318543,621298984,578433702,
886067101,407444984,727057915,6984504,843234790,122093498,876463450,142208808,814498485,504149395,393969843,95102817,503369336,655611756,586037118,182560468,43148191,332161331,636698918,822941302,
892493480,838728423,503130403,431638327,730989057,925060737,811216127,316645930,354712126,681291285,751117901,574127726,571801097,433506256,972842691,983984442,98023449,639312893,481810474,905421794,
452343642,783407363,534422143,172518371,852490959,273142641,533627356,989793526,110527397,334096401,924492434,827775204,528415572,905638872,89768217,318567875,793586547,536500715,245457983,151420390,
874507744,280340928,336385276,968293858,916250814,591314702,931761818,259429502,136059507,219641291,120755358,258916592,718917577,107171917,408057598,840260273,713116610,282957626,609452014,411949449,
925823950,758817172,747381768,813024695,818650548,424904887,946517578,208646085,403218853,945278586,329325588,985661125,136730689,653467402,911635273,648172567,817535132,448039705,498207267,713106349,
480696366,688170958,578301296,605779430,293561602,89211587,221244013,555467688,451328927,618254893,971996910,490973790,72615181,389704880,746724153,936195076,95023855,560844181,728360508,905691422,
170712947,227401900,262179183,800253138,561962853,319121517,751359733,302468831,36744230,495328744,552555902,272293296,764285908,40499409,871463542,642615379,210642711,759827354,658388455,314825854,
34263397,874792270,503814298,54385321,981558500,918727616,533970446,386392069,782468193,632388475,306399869,491149946,46030207,859519445,705527023,99736250,155947694,442422495,838225706,389569613,
166157083,117524870,929386956,879977857,696395985,410946954,217486914,327765878,827771049,534070140,850154729,622783551,998325860,279104721,779740386,683493565,898608802,914657774,658882632,352539328,
367240942,81301002,736076832,292312844,286483914,687138674,751242846,880522583,477807782,803375432,831292913,105761344,597458924,559884217,385699521,463074181,32027909,40774132,2063298,849526224,
794017395,179958326,341680882,459770584,417409957,656721857,35112784,681616244,853236027,791289576,577751300,991595908,365141715,440394011,225388346,850533892,424956735,892843251,889783384,599114008,
608262247,765088795,34231243,353447434,489958748,896793464,569130066,900640598,539833956,246399250,747549117,594363034,18130673,786695228,60796700,250415294,871114690,400385384,133988043,42296804,
626642615,775656548,621613147,396773748,289729806,301746222,103104670,889446938,238118220,964510506,978405839,140319691,117844290,241991919,363538264,709365741,738806816,999987346,986169892,992097060,
970334821,387615838,81182807,115131770,636755449,732886566,286241184,831762041,412961842,438266635,537359103,417521905,719981010,876249010,964468461,565755203,620541701,284920351,786986835,283183413,
714642299,663528939,209385373,785473562,35118680,668052504,316756671,392806068,943212124,506766137,970382636,425442659,24137129,835810160,703302363,99294215,982649379,654757989,615880040,421488673,
538613523,202184032,271372797,85938876,322571136,851231566,591498604,368910485,771308554,5180579,752004127,24589821,23424744,993015717,78232619,180651777,814899230,964994077,940691818,233827667,
374659900,788213154,650621768,745473124,320150953,942178690,355562759,337135956,552900734,414372544,934923176,586124058,154089618,595820597,895547362,921073254,280117908,176660594,267283523,517515188,
58173684,41710056,498551605,193445215,481800708,166034136,351911143,304890264,306466273,510513503,799629173,641476715,945129115,917412219,919248081,321998276,363807248,5945609,789153501,689983881,
977145897,67848173,384142185,209265532,543985312,962941421,470989887,359546218,62928701,14701750,504019226,531967757,667910086,905828384,520667577,924678694,523762159,573811160,37054941,438402164,
721784201,106498482,943551843,572003797,175309924,637665170,400347160,318059560,515275383,242580316,733016068,58423662,985786818,833575210,328087856,459796424,339688545,55611161,528613852,369292142,
734130861,181847437,529735265,710006992,626137872,9209086,274251083,376586879,668175412,753954855,348185950,130795342,603718899,947245032,876358036,497081417,162821219,330709351,417946907,658147507,
957680617,752014876,862061437,350517273,378208532,60433836,323307636,760103518,487597537,2411558,37356576,417776036,917889167,117134302,256512240,94929524,765541810,632097159,145279399,699051445,
486998598,358671914,675931510,169289884,794255277,587674951,524078565,372021474,550428070,984935102,964235003,996419231,665321582,486861531,765387552,450020438,990996656,196011632,86563134,754294557,
217338250,276658885,372396742,440211057,767623349,850360740,248699289,443807333,694088786,891526487,418025520,1756555,573499168,122985147,555241868,546935573,402714732,911553363,203094338,603992759,
494259229,163603221,667776398,684915919,371887794,220630204,914496828,184600149,666154837,754821013,463047618,276415733,9981899,664621458,283371852,807775999,934225571,970304356,691131571,195705196,
763245308,709537380,243275643,322406406,510471369,832950964,633607675,430829379,773972666,99706152,588353848,20238431,632024634,973062517,761730829,741780335,538677129,515945975,631513627,294052156,
219322291,286516732,394603484,318669184,566262435,233737119,862595752,295832769,534277907,592939483,357347749,439898219,36194982,781394057,606546678,594942670,838453748,293876844,639277462,130332963,
456675941,598237508,681590649,836293542,51232878,30967216,52070275,819474289,322813306,692766564,57401762,398518443,407991272,344113398,887939774,999630470,774794021,300830747,513276087,52143905,
118269852,329654665,577807508,884089299,256056030,543802122,296303710,617762012,23946621,298538874,349475137,65290160,171460404,86747354,779540867,624202471,257408727,434494542,885796489,172996134,
545463398,796599835,120181987,966704732,899724555,452202931,982849638,532466056,680288543,400331720,917731833,565090045,638815805,255470140,208109010,822626621,814098745,143126068,872177524,21933573,
427629605,595399197,558617482,734244469,779168363,446548899,442160676,280736470,142310575,728562130,119158425,628098277,660055301,566721279,503149473,284097952,240372926,75172066,720427845,193150837,
451773093,252491419,5610738,631887410,418872538,877255337,597206419,104721155,717962995,403606767,633182053,239416474,272579052,856823516,46531622,682656529,249066056,728886079,460843802,995611133,
952147969,874045558,85869805,549504627,720495238,404391511,613091305,421183771,822292707,585419857,111288266,288685600,350807459,731600725,922106875,326805315,119956721,101946345,555627356,102664153,
559875727,795578946,585931910,471277278,612485588,647298584,546672550,471121637,627061190,123151068,826638999,219703858,255799057,215995823,565326553,809128127,349385242,341073753,548503979,201664037,
852563190,231575132,103781371,125314514,699701615,834207488,996178055,969383659,710362398,204763452,323690417,680044618,484868443,403688684,412859850,655907501,299871568,391649701,714340575,643587224,
3920375,925101789,698467539,633271400,913028141,451856852,750824299,754288216,706240660,6651324,67810885,170674303,321204169,106714025,552211705,976742641,849733204,647334038,708763380,92650380,
433378456,797428586,539722656,159966794,158994690,895110923,440434274,437241095,954308601,343258197,94898840,695570338,483486670,505079348,371340716,114167291,42703090,599682957,217775876,175928333,
455707615,597645144,557579811,563001303,969393430,116577438,185055378,52353384,149365035,316694668,661000712,411339008,775506157,796382819,208277061,293267691,737547564,487766916,607376712,132971945,
930634998,552278922,91990819,42375141,150897017,276225587,244577329,706059393,991012914,966356353,891928824,276833414,735780531,845431196,740398,271300435,257684199,947788545,573177583,465426047,
912462594,14913124,542444156,790106092,434676586,391003871,668350072,226734533,833277172,918541766,432879313,702771359,287173297,833857736,935757786,987310420,40799780,662700539,790021172,586647332,
299685163,115804627,17582831,639847361,126019588,984458044,944801686,814313279,334222695,36070254,98050044,201353248,386511478,909740102,99281557,211748718,288468176,11823593,561599036,471322276,
484608150,411501867,984822349,716505537,753947753,736348999,651056298,689907021,105572207,67899911,520258510,35880030,674203508,837218270,125807293,196090539,615768254,720464309,470069534,305085045,
2965564,534462760,919968555,85858465,720834955,132270703,102551997,745422020,362324177,298745457,800559732,870371084,123857146,646112443,847991677,322453089,700901793,509533068,25675720,134135402,
183537927,842672616,956835604,404173188,952025161,113268097,2658741,193177287,572370726,198696166,157864180,419182112,691897411,281540958,946270414,753213505,934811398,745161993,316363271,514856621,
797770153,69262032,536863833,567823819,545450310,725454996,92296257,215522518,106115541,72833780,578555701,96623095,967184447,253538200,598476159,80626748,70798393,88322814,657398373,163433380,
709389462,972124841,58737689,362909476,421248248,769631996,799551962,614455980,886091803,710850416,466109384,666576172,820631465,286672502,129456417,976443552,874140770,144444817,240985642,605469703,
524023308,983535956,528003636,114872189,971380621,450904402,889298856,461242425,36580045,36666452,290709509,892113540,54822643,969664066,660691457,841528268,771711033,113032716,785886052,825606832,
238817272,859769340,206688041,338114807,709250775,28300128,112813450,746031018,533226136,758048490,238867440,185115382,53631047,405002849,759912198,455476834,501594168,437284588,187034800,917141162,
892052983,330715885,262915123,385618898,919321698,464387611,857393687,27473216,852659118,16227193,863039539,255887788,431836517,858566519,90718144,626234661,762705529,453709766,165159269,731642141,
212765997,749501340,420524832,98562670,306733892,74893697,795976800,82340717,622109155,35515269,731245059,762780634,684743588,409238306,62195298,839714533,864408738,41746760,916396900,528570184,
270363760,742104190,608690770,455938885,646923322,178321590,536757275,555143332,269025440,772925329,76684079,961805503,837799404,598524965,478534048,909414528,376133606,273381171,761913099,624894580,
124243466,856973598,611538098,224172745,435239281,745568731,272804737,607746906,670694102,567787801,447355411,356253599,96211618,80174641,188647081,626035925,776994054,62763577,797519179,44711392,
473409999,214647291,717761450,606739834,536562339,49544705,431681864,568991239,803856099,791368872,355674479,346313668,494566327,269794818,735787318,407101118,105405985,815827475,543290239,168861392,
306093819,157369495,370242833,893783997,834922229,314789190,325062287,584307986,394325146,496488360,928091268,878689884,546445937,994470198,7165779,946571523,608705247,79907146,593183092,384547940,
549368897,898708821,815669555,111735261,883115761,367089815,798348518,265338564,566605629,67137649,554708196,96219756,894047112,142380608,883569553,864465471,392765484,193355625,264654158,734954912,
718770601,173176165,754152104,672927770,552324736,283100102,880289836,339552073,493510491,868097596,538898063,987492084,957798660,312418956,888979635,356476143,71616092,935162559,248277392,568864600,
567913617,885842671,988842090,25217636,681733860,39957366,432600215,299863189,45779160,894556410,746921930,36464789,585979454,463809082,840188896,843589477,417060112,174572121,257362177,190275633,
738109863,761957568,75550124,301600916,728148637,164900629,799576238,54250085,441695463,421727601,257547033,872082918,704336346,565723700,496419962,621702047,8292123,520700966,677571245,508020884,
407986382,996566140,972363774,969831470,415613290,384888520,457714976,575372345,896705512,654467880,11664711,917896460,965702060,246902298,208943135,511239012,881516191,972156082,216538570,685385363,
943103277,904127598,689265402,482038882,385028675,276217189,665331937,550188850,273035625,376895045,461908299,41678316,399613106,445269059,570694300,506772002,179563720,566652725,553487310,789724145,
545571583,568133008,937750148,924346402,843770181,914138228,112178938,29575713,729310261,602005923,222271028,205042206,61927708,57550747,65892818,426637032,801511436,30632340,988847679,442080270,
903671223,490723198,780443788,666488804,215305630,522476550,569062054,77944186,370169878,221294249,717723967,113060541,684443697,588894649,719659475,562552416,52299217,428880461,93874868,466802664,
841468873,242306658,280720669,11430335,788813226,123248338,537459483,422858553,895888896,654368608,833833895,863882372,324516404,802486447,747634340,329236667,292348077,814144604,360266987,541164032,
968435904,111177461,152321616,844982622,368799406,186278931,899139495,104654044,251993555,498570307,566381236,598351262,14676609,369168153,205594714,914026425,587178017,876752195,849782923,844978779,
329066268,753133170,408971832,285422537,924716810,278820731,565778311,126054763,278879878,178591317,670977966,149623235,412248427,517056023,639073037,926494336,357025960,594228477,843860275,710220910,
52494433,841092731,13998805,333110174,240582132,715171124,128578038,101791574,361431536,596092173,312685506,692784669,448967208,681158443,732974767,48066987,26463665,880914424,493233268,270641951,
2113269,714714408,529950243,520106707,564594090,206290373,507884569,908220029,78637776,779319867,715632657,394470182,980597472,152993850,961196322,681642827,674015634,237584627,467550660,111388856,
425191969,30013676,768211946,559792318,258751277,509419560,602805476,332938247,853211342,532725776,812633479,62480581,436550788,730208660,236242966,601210025,681776998,401065243,604993642,918621914,
602493949,408981149,438625741,996484111,448470117,77698451,940827945,724404877,601206347,86583569,894805226,795400755,469503723,366195133,558846751,601464433,385031459,993851867,561893752,129132635,
497894769,89200452,799107396,855054005,672202744,709783452,327436662,641556949,381636229,746607121,261186239,632217561,605015714,819709336,667584382,147427465,721869190,173727446,462350789,579961720,
408000040,573466177,305264499,290546662,531054923,199465467,495731755,503427823,46091630,543568392,868353881,201937773,891146996,304489001,688495159,24064025,882804728,283380228,547850720,158016898,
611763331,279401748,260014407,237797394,338403964,985287868,756046666,238765082,888358324,882915383,980042402,373205975,548076502,138871481,784698877,985900407,960394902,500021620,826883587,449690896,
20104069,189077370,463202125,61050056,769516629,800164339,645566079,935648453,294035089,194390001,816760888,903922461,617719791,395411629,806013733,406642181,598856733,485004123,724561414,390479304,
825525481,498627915,861218227,203574974,511167025,320996839,577943834,491107686,390151677,581646015,205411154,90861142,613346934,550499712,938574240,928792163,643685355,33439239,732236128,914598517,
151732445,267870829,196616756,837286845,911254546,818293495,492920827,260740510,694786672,471866914,228905665,419287495,169200435,133979325,354449127,113268252,791271908,723815392,57117452,604603614,
703249474,69924060,657733166,512362637,628421745,805786488,505942924,708330512,766685418,265383856,875785429,212576414,690113152,378765312,861259274,89021407,238521452,567615800,271890840,341006300,
415038553,640823958,528302180,806859531,281672276,690049995,557778868,55465037,854877933,985293568,689837904,281830166,1126169,870461652,551795577,202653505,332470895,658936431,964335356,951892799,
102117102,529143168,837075746,976332793,99988787,420118082,64138186,931153144,548296809,927076232,419714933,575496277,997106766,196979373,453636904,668035276,219906872,824103882,386941588,862541747,
109175862,745608572,7440909,603453702,571950834,137102618,565289117,21443443,425395133,308213427,668550637,828985446,292366249,598154494,178767974,215924196,496983680,271293293,106529590,745042134,
960196809,412719168,507037767,247627464,95352774,823811189,375676484,719042093,703764387,917806036,543579315,214289452,870277948,615365883,573197285,743582429,858841171,240146275,653866761,167911190,
8071040,414364005,497377322,94611112,626821714,954364984,233539643,772930625,889752355,766192118,305753372,989599089,732895047,741153206,366575000,964394692,749222666,651388796,173285745,245712313,
84216743,45440069,483459436,606131420,331435369,143816730,950530376,937983912,428081037,734564864,19361219,148922017,550568547,68834813,821810889,57486190,10092869,756449095,72302380,288672955,
148197041,661470218,963390724,169502796,232340018,797768613,61330777,624588048,351464570,224590476,201645187,71700746,311565152,942125680,384692201,317340544,531255788,787075603,671233577,452302550,
937337941,328221054,78002447,747245231,860368390,761990136,473271222,548258276,930227121,808026102,472419427,172430487,971685190,604755260,333501613,803417656,899972607,604954843,852815227,387010414,
616346213,471320879,260468468,526702157,903657564,972036082,115948206,379256881,321920787,876337708,203687824,550277087,103880492,850085460,428635109,989771644,50579621,351329344,711820129,887723666,
426927339,525877567,885923110,569658403,857266904,102864386,590842313,392211111,220943544,290318020,169261918,638694929,547872362,670728499,562219901,414668749,914106171,96615548,204675890,543505114,
337403392,586096492,921079084,461958074,672795952,218454084,820936081,115731077,508157119,29704431,194378797,855044853,59769414,908164850,407732336,330205256,67892481,490021724,799082846,387171197,
692330957,54898428,573845410,963122479,408002342,421423178,700331937,982027681,900504911,842796901,805319018,250212049,961685549,902361126,69615810,351925380,385207656,409165861,123631934,544909871,
862119031,293537477,942945324,655968017,876419714,502646571,743870104,976530488,600629898,896075850,879024500,158223992,791357799,141388001,732898682,108439187,684867519,609693603,617422662,885898523,
892646944,271218948,667534164,596224119,296975600,590873974,736746501,287505675,946492565,423820100,292716452,845868328,951764297,911038138,312812153,891040515,380852553,374896135,179680953,671921878,
154882259,214717292,576817312,962151134,943609380,802347813,384130657,955673938,60988776,377724775,573513287,162310774,360742142,944444047,104408222,303324846,131925815,165328111,819377115,206989920,
994498707,257994002,339668080,704158236,794890133,890421136,960783632,523828357,501567737,76519194,548048501,188713074,100605341,71696041,432177565,910807276,491250836,268425554,304843692,486955799,
381494038,91815520,114245631,194421352,183634593,895175527,960675896,686452366,909849847,855584806,992088615,887850864,67762695,869460150,299667442,890540359,556009521,448123763,813393434,849133724,
559808005,613371158,197612886,876501069,446525049,793039013,746605271,939337618,661244640,716573062,280151054,753731586,622335720,310595972,39099625,680732063,617020077,594475227,580937148,621916884,
696940215,575890984,675354431,914960513,573727231,146403971,199814824,229201906,514568699,977023371,35122096,461212423,237776540,413774657,960988305,630363663,808354913,373267532,551601654,774395369,
533568064,238263757,71194417,844983298,858508245,753245056,369610788,603307098,261663549,919980972,777874751,515618192,150485829,893096765,3757964,648807648,756958547,875641282,27347664,565974056,
33164644,14654827,996614509,221991412,546854466,296737066,122980448,859077002,377013578,443614862,576886661,902359251,9430690,807710187,383361359,855445635,232265520,267707978,317587717,195990537,
31616657,124124042,800471730,271263145,487089466,994872912,794210083,193715301,667363937,710835710,697858049,736549406,525762583,211428066,242897352,229286269,795818317,440167974,388804058};

void init()
{
    int sum  = 0;
    FOR(i,1,100000000)
    {
        int ii = 1LL*i*i%MOD;
        int iii = 1LL*ii*ii%MOD;
        sum =  (sum + iii)%MOD;
        if(i%PARA==0) list[i/PARA-1] = sum;
    }
}

int Get4(int n)
{
    int ii = 1LL*n*n%MOD;
    int iii = 1LL*ii*ii%MOD;
    return iii;
    //n(n+1)(2n+1)(3n²+3n-1)/30
}

int GetSum4(int n)
{
    /*
    //n %= MOD;
    if(n%PARA==0) return li[n/PARA-1];
    int ans = li[n/PARA];
    int ed = (n/PARA+1) * PARA;
    FOR(i,n+1,ed+1)
    {
        ans -= Get4(i);
        if(ans<0) ans += MOD;
    }
    return ans;
    */
    long long a[] = {n,n+1,(2LL*n+1)%MOD,(3LL*n*n%MOD+3LL*n-1)%MOD,233333335};
    int ans = 1;
    REP(i,5) ans = a[i]*ans%MOD;
    return ans;
}
vector<int> prime;
void GetDivide(int n)
{
    prime.clear();
    for(int i=2;i*i<=n;++i)
    {
        if(n%i==0)
        {
            prime.push_back(i);
            while(n%i==0) n/=i;
        }
    }
    if(n!=1) prime.push_back(n);
}

int Dfs(int dep,int pre,int cnt,int n)
{
    if(dep==prime.size())
    {
        //printf("dep=%d pre=%d cnt=%d n=%d\n",dep,pre,cnt,n);
        if(cnt==0||pre>n) return 0;
        int ans = (cnt&1)?1:-1;
        ans = 1LL*Get4(pre)*GetSum4(n/pre)%MOD*ans;
        return ans;
    }
    long long ans = 0;
    ans += Dfs(dep+1,pre*prime[dep],cnt+1,n);
    ans += Dfs(dep+1,pre,cnt,n);
    if(ans>=MOD) ans -= MOD;
    else if(ans<0) ans += MOD;
    return ans;
}
int GetAns(int n)
{
    GetDivide(n);
    int ans = GetSum4(n-1)-Dfs(0,1,0,n-1);
    if(ans<0) ans+=MOD;
    return ans;
}
int main()
{
/*
    freopen("tx.txt","w",stdout);
    init();
    printf("{");
    REP(i,N)
    {
        cout<<list[i];
        if(i!=N-1) putchar(',');
        if(i%20==0) puts("");
    }
    puts("};");
*/
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        cout<<GetAns(n)<<endl;
    }
	return 0;
}
